package leetcode.队列和栈.单调队列;

import java.util.ArrayDeque;
import java.util.Deque;

public class Leetcode862 {
    public int shortestSubarray(int[] A, int K) {
        int[] preSum = new int[A.length+1];
        //前缀和
        for(int i = 0;i<A.length;i++){
            preSum[i+1] = preSum[i]+A[i];
        }
        Deque<Integer> de = new ArrayDeque<>();
        int min = A.length+1;
        for (int i = 0; i <= A.length; i++) {
            while(!de.isEmpty()&&preSum[i]<=preSum[de.peekLast()]){
                de.removeLast();
            }
            while(!de.isEmpty()&&preSum[i]-preSum[de.peekFirst()]>=K) {
                int tmp = de.removeFirst();
                min = Math.min(min,i-tmp);
            }
            de.offer(i);
        }
        return min;
    }
}
